/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package org.murillo.chufa;

import org.murillo.chufa.entry.CacheEntryFactory;
import org.murillo.chufa.entry.CacheEntryList;
import org.murillo.chufa.entry.CacheEntry;
import org.murillo.chufa.entry.SoftValueWeakKeyCacheEntry;
import org.murillo.chufa.entry.WeakKey;
import java.lang.ref.ReferenceQueue;
import java.util.*;
import java.util.concurrent.atomic.AtomicLong;
import org.apache.commons.collections4.map.LRUMap;
import org.murillo.chufa.datastructures.BoundedBag;
import org.murillo.chufa.datastructures.FifoBoundedBag;
import org.murillo.chufa.datastructures.LRUWeakIdentityHashMap;
import org.murillo.chufa.datastructures.WeakFifoBoundedBag;

/**
 *
 * @author Elisa
 */
public class Cache<K, V> {

    protected Map<K, CacheEntry<K, V>> softmap;
    public CacheEntryList<K, V> hardlist;
    protected float[] profitArray;
    protected int hardCapacity;
    protected ReferenceQueue refQueue = new ReferenceQueue();
    protected AtomicLong tickCounter = new AtomicLong(0L);
    protected long maintenancePeriod = 3;
    protected BoundedBag<K> futureBag;
    protected boolean defaultSecureOnPut;

    protected int hits = 0;
    private int misses = 0;

    //FOR WEAK VALUES
    protected int softCapacity;
    protected ReferenceQueue keyQueue;

    private final boolean weak;

    public Cache(int hardCapacity) {
        this(hardCapacity, -1, false);
    }

    protected Cache(boolean weakKeys) {
        this.weak = weakKeys;
    }

    public Cache(int hardCapacity, boolean isWeak) {
        this(hardCapacity, -1, isWeak);
    }

    public Cache(int hardCapacity, int softFactor, boolean isWeak) {
        this.weak = isWeak;
        this.defaultSecureOnPut = false;
        this.hardCapacity = hardCapacity;
        this.hardlist = new CacheEntryList<K, V>(hardCapacity);
        this.profitArray = new float[hardCapacity];
        long softc = ((long) softFactor) * hardCapacity;
        if (softFactor <= 1 || softc > Integer.MAX_VALUE) {
            softCapacity = Integer.MAX_VALUE;
        } else {
            softCapacity = (int) softc;
        }
        if (isWeak) {
            keyQueue = new ReferenceQueue();
            this.futureBag = new WeakFifoBoundedBag<K>(hardCapacity - (1 + hardCapacity >> 2));
            if (softFactor > 1) {
                this.softmap = new LRUWeakIdentityHashMap<K, CacheEntry<K, V>>(softCapacity, 0.75f);
            } else {
                this.softmap = new HashMap<K, CacheEntry<K, V>>(hardCapacity, 0.75f);
            }
        } else {
            this.futureBag = new FifoBoundedBag<K>(hardCapacity - (1 + hardCapacity >> 2));
            if (softFactor > 1) {
                this.softmap = new LRUMap<K, CacheEntry<K, V>>(softCapacity, 0.75f, true) {                    
                    @Override
                    protected boolean removeLRU(LinkEntry<K, CacheEntry<K, V>> eldest) {
                        if (size() >= this.maxSize()) {
                            if (eldest.getValue().getHard() == null) {
                                eldest.getValue().dispose();
                                return true;
                            }
                        }
                        return false;
                    }
                };
            } else {
                this.softmap = new HashMap<K, CacheEntry<K, V>>(hardCapacity, 0.75f);
            }
        }
    }

    public long getMaintenancePeriod() {
        return maintenancePeriod;
    }

    public void setMaintenancePeriod(long maintenancePeriod) {
        this.maintenancePeriod = maintenancePeriod;
    }

    public boolean isDefaultSecureOnPut() {
        return defaultSecureOnPut;
    }

    public void setDefaultSecureOnPut(boolean defaultSecureOnPut) {
        this.defaultSecureOnPut = defaultSecureOnPut;
    }

    public int getHardSize() {
        return hardlist.getCurrentsize();
    }

    public int getSoftSize() {
        return softmap.size();
    }

    public V putAndUse(K key, V value, long cost) {
        return put(key, value, cost, true);
    }

    public V put(K key, V value, long cost) {
        return put(key, value, cost, defaultSecureOnPut);
    }

    public synchronized V put(K key, V value, long cost, boolean secureOnPut) {
        long tickStamp = tick();
        CacheEntry<K, V> get = softmap.get(key);
        if (get != null) {
            V hard = get.getHard();
            if (hard != null) {
                int indexOf = hardlist.indexOf(get);
                if (indexOf < 0) {//Existe pero está borrado
                    hardlist.recycle(get);
                    indexOf = hardlist.getCurrentsize() - 1;
                }
                if (hard != value) {
                    get.dispose();
                    CacheEntry<K, V> newEntry = CacheEntryFactory.newCacheEntry(weak, key, value, refQueue, cost, get);
                    //newEntry.setHard(hard);
                    CacheEntry<K, V> put = softmap.put(key, newEntry);
                    newEntry.setHard(value);
                    hardlist.set(indexOf, newEntry);
                }
                return hard;
            } else {
                V soft = get.get();
                if (soft != value) {
                    get.dispose();
                    CacheEntry<K, V> newEntry = CacheEntryFactory.newCacheEntry(weak, key, value, refQueue, cost, get);
                    softmap.put(key, newEntry);
                    if (secureOnPut) {
                        newEntry.setHard(value);
                        addHardAndEvictIfDoesntFit(newEntry);
                    }
                }
                return soft;
            }
        } else {
            CacheEntry<K, V> newEntry = CacheEntryFactory.newCacheEntry(weak, key, value, refQueue, keyQueue, cost, tickStamp);
            softmap.put(key, newEntry);
            if (secureOnPut) {
                newEntry.setHard(value);
                addHardAndEvictIfDoesntFit(newEntry);
            }
            return null;
        }
    }

    public V getQuiet(K key) {
        CacheEntry<K, V> get = softmap.get(key);
        if (get != null) {
            return get.get();
        } else {
            return null;
        }
    }

    public synchronized V get(K key) {
        tick();
        CacheEntry<K, V> get = softmap.get(key);

        if (get != null) {
            hit(get);
            V hard = get.getHard();
            if (hard != null) {
                futureBag.remove(key);
                return hard;
            } else {
                V soft = get.get();
                if (soft != null) {
                    get.setHard(soft);
                    addHardAndEvictIfDoesntFit(get);
                } else {
                    softmap.remove(get.getKey());
                    get.dispose();
                }
                futureBag.remove(key);
                return soft;
            }
        } else {
            miss();
            futureBag.remove(key);
            return null;
        }
    }

    protected void runMaintenance() {
        if (weak) {
            WeakKey<K> wk;
            while ((wk = (WeakKey<K>) keyQueue.poll()) != null) {
                CacheEntry<K, V> remove = softmap.remove(wk);
                remove.dispose();//Podría estar en hardlist
            }
            SoftValueWeakKeyCacheEntry<K, V> sv;
            while ((sv = (SoftValueWeakKeyCacheEntry<K, V>) refQueue.poll()) != null) {
                wk = sv.getWeakKey();
                if (wk != null) {
                    softmap.remove(wk);
                }
            }
            ((WeakFifoBoundedBag) futureBag).runMaintenance();
        } else {
            CacheEntry<K, V> sv;
            while ((sv = (CacheEntry<K, V>) refQueue.poll()) != null) {
                K key = sv.getKey();
                if (key != null) {
                    softmap.remove(key);
                }
            }
        }
    }

    private long tick() {
        long t = tickCounter.incrementAndGet();
        if (t % maintenancePeriod == 0) {
            runMaintenance();
        }
        return t;
    }

    private void addHardAndEvictIfDoesntFit(CacheEntry<K, V> entry) {
        if (hardlist.isFull()) {
            evict(1 + (hardCapacity >> 2));
        }
        hardlist.add(entry);
    }

//    private boolean addHardAndEvictIfWorthy(SoftValueCacheEntry<K, V> entry) {
//        if (hardlist.isFull()) {
//            return replaceIfWorthy(entry);
//        } else {
//            hardlist.add(entry);
//            return true;
//        }
//    }
//
//    private boolean replaceIfWorthy(SoftValueCacheEntry<K, V> entry) {
//        SoftValueCacheEntry<K, V>[] hardArray = hardlist.getArray();
//        long tickStamp = tickCounter.get();
//        float entryworth = entry.getProfit(tickStamp);
//        for (int i = hardlist.currentsize - 1; i >= 0; i--) {
//            SoftValueCacheEntry<K, V> aux = hardArray[i];
////            synchronized (aux) {
//            float profit = aux.getProfit(tickStamp);
//            if (entryworth <= profit) {
//                aux.setHard(null);
//                hardlist.array[i] = entry;
//                return true;
//            }
////            }
//        }
//        return false;
//    }
    private void evict(int n) {
        if (n > hardlist.getCurrentsize()) {
            n = hardlist.getCurrentsize();
        }
        //Ordenamos las matrices
        sortVectors(n);
        //Evitamos que se evacuen los futuros
        preventFutureEviction(n);
        //Eliminamos los últimos n elementos
        hardlist.freeLastN(n);
    }

    private static void selectKthHighest(float[] arr, int k, int from, int to, CacheEntry[] hardArray) {

        // if from == to we reached the kth element
        while (from < to) {
            int r = from, w = to;
            float mid = arr[(r + w) / 2];

            // stop if the reader and writer meets
            while (r < w) {

                if (arr[r] <= mid) { // put the large values at the end
                    float tmp = arr[w];
                    arr[w] = arr[r];
                    arr[r] = tmp;

                    CacheEntry aux = hardArray[w];
                    hardArray[w] = hardArray[r];
                    hardArray[r] = aux;

                    w--;
                } else { // the value is smaller than the pivot, skip
                    r++;
                }
            }

            // if we stepped up (r++) we need to step one down
            if (arr[r] < mid) {
                r--;
            }

            // the r pointer is on the end of the first k elements
            if (k <= r) {
                to = r;
            } else {
                from = r + 1;
            }
        }
    }

    private static void selectKthLowest(float[] arr, int k, int from, int to, CacheEntry[] hardArray) {

        // if from == to we reached the kth element
        while (from < to) {
            int r = from, w = to;
            float mid = arr[(r + w) / 2];

            // stop if the reader and writer meets
            while (r < w) {

                if (arr[r] >= mid) { // put the large values at the end
                    float tmp = arr[w];
                    arr[w] = arr[r];
                    arr[r] = tmp;

                    CacheEntry aux = hardArray[w];
                    hardArray[w] = hardArray[r];
                    hardArray[r] = aux;

                    w--;
                } else { // the value is smaller than the pivot, skip
                    r++;
                }
            }

            // if we stepped up (r++) we need to step one down
            if (arr[r] > mid) {
                r--;
            }

            // the r pointer is on the end of the first k elements
            if (k <= r) {
                to = r;
            } else {
                from = r + 1;
            }
        }
    }

    // Implementing Fisher–Yates shuffle
    static void shuffleArray(float[] ar) {
        Random rnd = new Random();
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // Simple swap
            float a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }

    private void preventFutureEviction(int n) {
        final int frontierIndex = hardlist.getCurrentsize() - n;
        int saveIndex = frontierIndex - 1;
        int doomIndex = hardlist.getCurrentsize() - 1;
        CacheEntry<K, V>[] array = hardlist.getArray();
        while (doomIndex >= frontierIndex) {
            CacheEntry<K, V> c1 = array[doomIndex];
            K key = c1.getKey();
            if (futureBag.contains(key)) {
                while (saveIndex >= 0) {
                    CacheEntry<K, V> c2 = array[saveIndex];
                    if (futureBag.contains(c2.getKey())) {
                        saveIndex--;
                    } else {
                        //Swap
                        array[saveIndex] = c1;
                        array[doomIndex] = c2;
                        break;
                    }
                }
            }
            doomIndex--;
        }

    }

    public void addFutureUse(K key) {
        futureBag.add(key);
    }

    private void sortVectors(int n) {
        CacheEntry<K, V>[] hardArray = hardlist.getArray();
        long tickStamp = tickCounter.get();
        for (int i = 0; i < hardlist.getCurrentsize(); i++) {
            profitArray[i] = hardArray[i].getProfit(tickStamp);
        }

        //Ordenamos las matrices
        int currentsize = hardlist.getCurrentsize();
        selectKthLowest(profitArray, currentsize - n, 0, currentsize - 1, hardArray);
        for (int i = currentsize - 1; i > currentsize - n; i -= 2) {
            selectKthHighest(profitArray, i - 1, currentsize - n, i, hardArray);
        }
    }

    private void hit(CacheEntry<K, V> get) {
        get.hit();
        this.hits++;
    }

    private void miss() {
        this.misses++;
    }

    public float getHitRatio() {
        return ((float) hits) / (hits + misses);
    }
    
    public void clear(){
            softmap.clear();
    hardlist.clear();
    refQueue = new ReferenceQueue();
    tickCounter.set(0);
    futureBag.clear();
    }
}
